1. Field of the Industrial Application
The present invention relates to a Viterbi decoder which is used for performing the socalled most likelihood decoding operation for convolutional codes.
2. Description of the Related Art
The Viterbi decoder is used for the most likelihood decoding technique for the convolutional codes. The Viterbi decoder is operated to select as the most likely path the path at the closest distance to the input code series from the paths of the known code series and to derive the decoded data for the selected path. The Viterbi decoding operation offers a high capability of correcting errors randomly appearing in a speech channel and in particular offers a far greater coding gain in combination with a flexible decoding and demodulating system. For example, a satellite communications system, which is subject to the influence of interference waves and whose power is strictly restricted, uses the convolutional codes as error-correcting codes and thus employs the Viterbi decoder for decoding the data signal.
The Viterbi decoding algorithm will be briefly described below.
For example, consider that the generating polynomials are G.sub.0 (D)=1+D.sup.2 and G.sub.1 (D)=1+D+D.sup.2, the coding rate is R=1/2, and a constraint length is K=3. The arrangement of the decoder for generating such codes is illustrated in FIG. 1. In FIG. 1, the input data is sequentially delayed by delay elements 301 and 302, each of which may be composed of a flip-flop, for example. Then, the delayed data of the delay element 302 is added to the input data by an adder 303. The adder 303 operates to add the input data to the data fed by the delay element 302 to feed the added data as an output G.sub.0. Adders 304 and 305 are provided for adding the input data to the data fed by the delay element 301 and 302 to feed the added data as an output G.sub.1.
Assuming that the outputs of the delay elements 301 and 302 provided in the coder are b.sub.1 and b.sub.2 respectively, the coder may take as its state four states of (00), (01), (10), and (11). Each state constantly has just two transitive states to be given if an input is applied to the state.
More specifically, when an input is 0, if the current state is (00) or (10), the state is transited to (00) and if the current state is (01) or (11), the state is transited to the state (10). When an input is 1, if the current state is (00) or (10), the state is transited to the state (01) and if the current state is (01) or (11), the state is transited to the state (11).
These state transitions are illustrated in the Trellis diagram of FIG. 2. As shown, a branch of a solid line indicates the transition given when the input is 0, while a branch of a broken line indicates the transition given when the input is 1. The figure noted along each branch means the code (G.sub.0, G.sub.1) shown in FIG. 1, which are output when the transition takes place in the branch.
As is obvious from FIG. 2, at the time of the transition to each state, two paths always lead to the state. In the Viterbi decoding algorithm, the decoding operation is executed to continuously select the most likely path of two paths leading to the state until a given time length, detect as a surviving path the most likely path from the selected paths selected in each state, and decode the received codes on the surviving paths.
The Viterbi decoder for decoding the convolutional codes based on the Viterbi algorithm includes a branch metric calculator for calculating a metric between the transmission series and each branch, an ACS (Adder, Comparator, Selector) operating unit for selecting the surviving path and calculating a path metric of the selected path, a path metric storage unit for storing a value of a path metric of each state, a path memory for storing an output of the selected path, and a most likelihood determining unit for detecting an address of the most likelihood path metric and control a path memory based on the address.
The ACS operating unit is served to select the surviving path in each state according to the so-called path metric transition diagram and calculate the path metric of the surviving path. The path metric transition diagram is created on the Trellis diagram of FIG. 2.
The path metric transition diagrams shown in FIGS. 3A and 3B are created on the Trellis diagram of FIG. 2. For the Trellis diagram of FIG. 2, the paths that lead to the state (00) are a path appearing when a code (00) is generated in the state (00) and another path appearing when a code (11) is generated in the state (10). Hence, in a case that the state value (path metric) of the previous time point is S00 (old) or S10 (old) and the branch metric is BM00 or BM11, the path metric S00 (new) of the current state (00) is any one of: EQU S00 (new)a=S00 (old)+BM00 EQU S00 (new)b=S10 (old)+BM11
That is, the selected path has a smaller one of these two path metrics S00 (new)a and S00 (new)b located on the calculating way. These path metrics are fed as a path metric S00 (new) of the current state (00).
The paths that lead to the state (01) are a path appearing when the code (11) is generated in the state (00) and another path appearing when the code (00) is generated in the state (10). Hence, the path metric S00 (new) in this state is any one of: EQU S01 (new)a=S00 (old)+BM11 EQU S01 (new)b=S10 (old)+BM00
The paths that lead to the state (10) are a path appearing when the code (01) is generated in the state (01) and another path appearing when the code (10) is generated in the state (11). Hence, the path metric S10 (new) in this state is any one of: EQU S10 (new)a=S01 (old)+BM01 EQU S10 (new)b=S11 (old)+BM10
The paths that lead to the state (11) are a path appearing when the code (10) is generated in the state (01) and another path appearing when the code (01) is generated in the state (11). Hence, the path metric S11 (new) in this state is any one of: EQU S11 (new)a=S01 (old)+BM10 EQU S11 (new)b=S11 (old)+BM01
On these rules are created the path metric transition diagrams as shown in FIGS. 3A and 3B.
The conventional Viterbi decoder has been known where the ACS operation is executed in a time-divisional manner and the path metric memory for storing the path metric value obtained as a result of the ACS operation utilizes a RAM (Random Access Memory). This type of Viterbi decoder is served to allocate to one address of the RAM a path metric value that is used for the ACS operation at a next time point to the time when the ACS operational is done. This means that the path metric value of one state is stored in one address of one RAM.
In this operation, one ACS operation is executed to create a new path metric value from the path metrics of the previous two states. This means that it is necessary to make three accesses to the RAM for one ACS operation for the purpose of reading the previous two path metrics and writing one new path metric. The so-called dual port RAM may be used for separating the write and the read and doing them in parallel. However, even the arrangement with the dual port RAM needs two reading operations. Therefore, the conventional Viterbi decoder that performs the foregoing operation needs lots of memory accesses and thus a high-speed RAM and address generating circuit. These high-speed units are obstacles to saving the power consumption and speeding up the overall operation.